\section{Simulation Results}
\label{sec:results_mm}

\subsection{Simulation Setup}
Table \ref{tab:benchinfo} shows the number of state elements and combinational gates are listed in columns 2 and 3, respectively. The largest one is {\tt des\_perf} with about 150K gates with 8K sequential components. Therefore, due to the larger number of sequential components we use a trace buffer bandwidth of $B=64$ in our experiments. (Previous works used $B=32$ for much smaller-sized benchmarks.) We also used a capture window of $2048$ cycles which corresponds to the buffer bandwidth. We note both this buffer bandwidth and capture window are considered as reasonable values for on-chip trace buffer \cite{YangVN12}.
%The control signal for {\tt des\_perf} is a {\tt decrypt} signal which creates two modes with significantly different restoration maps.
Column 4 lists the number of modes defined by the control signals. (In defining the modes, we excluded obvious control signals such as reset by assuming reset is always inactive.)

\begin{table}[t]
  \centering
  \caption{Benchmark Information}
    \begin{tabular}{cccccc}
    \toprule
          &  \#FF & \#Gates &  M     & M$_{merged}$ &   \\
    \midrule
    {\tt S38584}   & 1166  & 10552 &  2     & 2     & ISCAS'89 \\
    \rowcolor{LightCyan}
    {\tt S35932}   & 1728  & 11032 &  4     & 2     & ISCAS'89 \\
    {\tt b17}      & 1317  & 33888 &  4     & 4     & IWLS'05 \\
    {\tt b18}      & 3020  & 119762&  2     & 2     & IWLS'05 \\
    \rowcolor{LightCyan}
    {\tt dsp}      & 3605  & 54730 &  8     & 2     & IWLS'05 \\
    \rowcolor{LightCyan}
    {\tt DMA}      & 2192  & 36556 &  8     & 4     & ISPD'12 \\
    {\tt des\_perf}& 8802  & 149066&  2     & 2     & ISPD'12 \\
    \bottomrule
    \end{tabular}%
  \label{tab:benchinfo}
\end{table}%

When implementing IteM, we applied the mode merging procedure explained in Section \ref{sec:merging} with a similarity threshold of 0.7. The number of modes after merging is reported in column 5. Mode merging reduced the number of modes in 3 of the benchmarks which are shown by highlighted rows. For example, in {\tt dsp} mode merging allowed reducing the number of modes from 8 to 2. We verified that the identified signals are control signals in different ways. First, using the similarity metric given by Equation \ref{eq:similar}, we observed difference in the restoration maps in the operation modes defined by the identified control signals, as can be seen from Table \ref{tab:benchinfo} columns 4 and 5. Moreover, by solving the Single-mode Trace Signal Selection (SMTS) problem for each mode, we observed either significant variation in the corresponding single-mode restoration ratio $SRR^m$, and a significant difference in the generated solutions (i.e., the selected trace signals).

We compared the following techniques in our simulations:
\begin{itemize}
\item IteM: Our proposed multi-mode selection procedure
\item HYBR: Single-mode selection procedure of \cite{LiD13,LiD14TCAD}
\item RATS: Single-mode selection procedure of \cite{BasuM13}
\item SimF: Single-mode simulation-based procedure of \cite{ChatterjeeMB11}
\item HYBRM: Extension of HYBR for multi-mode signal selection
\end{itemize}
IteM was implemented as explained in Section \ref{sec:item} with a maximum radius of $R=3$ and includes the mode merging step given in Section \ref{sec:merging}. HYBR, RATS and SimF are based on solving the SMTS problem for the same (promising) start mode identified for IteM. SimF is a variation of the simulation-based approach of \cite{ChatterjeeMB11} which selects the trace signals based on a forward greedy selection strategy. (We were not able to generate a solution within a 24-hour runtime limit for larger benchmarks, using the original selection procedure of \cite{ChatterjeeMB11} based on backward elimination of not-promising signals.)

HYBRM is an alternative multi-mode selection procedure. It follows forward greedy trace signal selection and runs for $B$ iterations, selecting one trace signal at each iteration. At each iteration, first, the top 3\% of state elements with the highest value of the multi-mode impact weight given by Equation \ref{eq:mmiw} are selected. Among these candidates, X-Simulation is used to find the best one which provides the highest $MSRR$ value. HYBRM is a direct extension of HYBR incorporating multi-mode impact weights and $MSRR$.

%Also note that we tried to compare our results with other existing approaches like \cite{YangT12, YangVN12, ChatterjeeMB11}. However due to the scalability issue, these approaches could not finish within a comparable runtime as above approaches took. Therefore, we did not compare with them in this work.

In addition, to generate a reference as an upper bound for the attainable $MSRR$, we also used the procedure given in Section \ref{sec:ref} by generating $M$ distinct single-mode optimized solutions and adding their (individual) $SRR^m$ $\forall m=1,\ldots,M$. To obtain the single-mode solution in each mode $m$ for each benchmark, we ran (in parallel), each of the single-mode techniques (i.e., HYBR, RATS, SimF) and selected the best solution to compute the highest $SRR^m$ for mode $m$. We denote this reference case by REF.

% Table generated by Excel2LaTeX from sheet 'Sheet3'
\subsection{Comparison of Solution Quality}
We compare the solution quality of the described techniques using the multi-mode restoration ratio $MSRR$ given by Equation \ref{eq:msrr}. The $MSRR$ of a trace signal selection solution is computed using X-Simulation over $M$ modes for the capture window of 2048 cycles. The results are reported in Table \ref{tab:msrr}. $MSRR$ of REF is given in column 2. For the remaining columns, an $MSRR$ ratio, normalized to REF is given.

\begin{table}[t]
  \centering
  \caption{Comparison of MSRR normalized to the reference case (REF)}
    \begin{tabular}{ccccccc}
    \toprule
                    &  {REF} & RATS & HYBR & SimF & HYBRM & IteM \\
    \midrule
    {\tt S38584}    &  {25.20} & 0.86 & 0.85 & 0.95 & 0.95  & 1.00 \\
    \rowcolor{LightCyan}
    {\tt S35932}    &  {66.40} & 0.64 & 0.74 & 0.65 & 0.91  & 0.91 \\
    {\tt b17}       &  {7.90}  & N/A  & 0.62 & 0.58 & 0.76  & 0.94 \\
    {\tt b18}       &  {5.90}  & N/A  & 0.50 & 0.92 & 0.61  & 0.80 \\
    \rowcolor{LightCyan}
    {\tt dsp}       &  {42.80} &  N/A & 0.41 & 0.88 & 0.37  & 0.92 \\
    \rowcolor{LightCyan}
    {\tt DMA}       &  {50.67} & 0.76 & 0.88 & 0.89 & 0.84  & 0.92 \\
    {\tt des\_perf} &  {77.60} &  N/A & 0.97 & 0.98 & 0.98  & 0.99 \\
    \midrule
    Average         &  \textbf{1.0} & & \textbf{0.71} & \textbf{0.83}  &
    \textbf{0.77}   & \textbf{0.93}\\
    \bottomrule
    \end{tabular}
  \label{tab:msrr}%
\end{table}%

As can be seen, IteM consistently performs better than all the other techniques except in {\tt b18} where it performs worse than SimF but it still has an $MSRR$ of 0.8 of REF. Also SimF takes 20X longer to generate a solution in this benchmark compared to IteM. The $MSRR$ values of IteM are on average 0.93 of the $MSRR$ of REF.

HYBRM which explicitly considers multi-mode selection, often performs better than HYBR, but it is sometimes worse than SimF, except in {\tt S35932} and {\tt b17} in which it performs significantly better than SimF. However, we note HYBRM also has a runtime much faster than SimF, as we report in the next experiment.

We only reported results of RATS in 3 benchmarks as shown in the table. These results for RATS are similar to or worse than HYBR. We note, even though RATS could quickly generate a solution in these 3 benchmarks, it was not able to generate a solution for the other ones, which were all from ISPD'12 and IWLS'05 benchmarks, after imposing a 24-hour runtime limit. (We note while implementing RATS, the procedure for setting a custom parameter used in a step to extend the graph edge weights was not provided in \cite{BasuM13}. We therefore tuned this parameter for each benchmark to achieve the best possible implementation of RATS for that benchmark, for the purpose of comparison in our experiments.)

%As can be seen from the table, Rats has worse solution quality as compared with the other approaches. This is as expected since metric-based algorithms cannot fully consider the signal correlation. Note that only the results of {\tt S35932} and {\tt S38417} are reported because Rats cannot finish within a runtime limit of 4 hours for our selected benchmarks in the IWLS'05 and ISPD'12 contest. More details will be discussed in the following runtime comparison section.

%HYBR has better solution quality than SimF in most benchmarks except for {\tt S38584} and {\tt dsp}. This is also why when obtaining an upper bound for Ref, the better solution between these two is chosen.

\exclude{
When comparing HYBRM with HYBR, HYBRM has significantly better solution quality in
relatively small benchmarks like {\tt S35932}, {\tt S38584} and {\tt
  b17}. In general, HYBRM has
better solution quality (0.77 of the Ref on average) than HYBR (0.71 of the
Ref on average), which shows that the modified multi-mode impact weight can
actually help identifying the top candidates that are good for maximizing
$MSRR$.  SimF exposes a similar trend as HYBR, since ConM has much better solution quality compared with SimF
for small benchmarks. For large benchmarks, SimF always performs
better, and is 0.83 of the Ref on average. But it should be pointed out that the
better solution quality of the SimF is obtained through a sacrifice for much longer
runtime. For example for {\tt b18}, with a 1.5X improvement in $MSRR$, SimF
takes 20X more time to finish.
}

\exclude{
Column 7 shows the solution quality of the IteM. Note that for {\tt
  S35932}, {\tt dsp} and {\tt DMA}, we report the $MSRR$ values of these
three benchmarks after mode merging is applied. It can be seen that IteM
is consistently better than all other methods except for {\tt b18}, which is
due to the bad initial point generated by HYBR. Anyhow, this has shown that an iterative approach based on perturbing to improve restoration over all the modes is a
more suitable strategy than a constructive one. Also, recall that HYBR
offers the initial starting point for IteM, and the average
improvement of IteM over HYBR for all benchmarks is 0.22.  When compared
with the Ref, IteM is 0.93 of Ref on average, which is the highest among all approaches.

To show the effectiveness of IteM in identifying a suitable starting mode to generate its initial solution, i.e., $m_{start}$ given in Section \ref{sec:item}, we report the percentage of the state elements which are shared in the initial solution and the final solution of IteM. This is given in the last column of Table \ref{tab:msrr}, denoted by IteM-Shr. Interestingly, on average 41\% of the state elements are the same as the initial solution. This may also confirm the suitability of an iterative strategy over a constructive one. (More analysis of IteM will be presented later.)
%between 23 to 50 and on average 41
}

\subsection{Comparison of Runtime}
Here we compare the runtime of different techniques. All techniques were implemented in C++ and ran on a quad-core CPU using multi-threading. Specifically, our setup allowed up to 8 parallel threads to run simultaneously. This parallel implementation was utilized when running X-Simulation using bit-wise parallelism procedure given in \cite{KoN09}. This same implementation of X-Simulation was utilized in the source codes of all our trace signal selection strategies.

% Table generated by Excel2LaTeX from sheet 'Sheet3'
\begin{table}[t]
  \centering
  \caption{Comparison of Runtime (min)}
    \begin{tabular}{cccccc}
    \toprule
          & \multicolumn{1}{c}{RATS} & \multicolumn{1}{c}{HYBR} &
          \multicolumn{1}{c}{SimF} & \multicolumn{1}{c}{HYBRM} & \multicolumn{1}{c}{IteM}\\
    \midrule
%          & RUN & RUN & RUN & RUN & $MW_f$ & RUN & \#Ite \\
    {\tt S38584}    & 0.1 & 2    & 19  & 4     & 13  \\
    \rowcolor{LightCyan}
    {\tt S35932}    & 0.1 & 2    & 14  & 5     & 15  \\
    {\tt b17}       & 24+ & 1    & 19  & 4     & 24  \\
    {\tt b18}       & 24+ & 4    & 2151& 119   & 90  \\
    \rowcolor{LightCyan}
    {\tt dsp}       & 24+ & 2    & 92  & 28    & 251 \\
    \rowcolor{LightCyan}
    {\tt DMA}       & 5   & 7    & 99  & 38    & 125 \\
    {\tt des\_perf} & 24+ & 16   & 469 & 24    & 94  \\
    \bottomrule
    \end{tabular}%
  \label{tab:runtime_mm}
\end{table}%

The runtime results are reported in Table \ref{tab:runtime_mm} given in minutes. As can be seen, RATS has the fastest runtime (fraction of a minute) for the two ISCAS'89 benchmarks and only 5 minutes for {\tt DMA}. However, it was not able to generate a solution for the remaining benchmarks after a 24-hour runtime limit. We found out that in these benchmarks, the time spent by RATS on finding ``the exact paths'' of all pairs of state elements to compute the edge weights create the runtime bottlenecks.  Among the rest, HYBR runs much faster due to its hybrid nature which incorporates fast metrics with a small number of X-Simulations. In contrast SimF which is purely based on X-Simulation usually has the highest runtimes in most of the benchmarks. HYBRM has a runtime between the HYBR and SimF in all benchmarks. It takes more than HYBR due to the extensions to evaluate the multi-mode impact weight and compute $MSRR$.


%To further analyze the runtime of ConM, we reported the amount of time spent on evaluating the multi-mode impact weights over all the iterations. This is denoted by $MW_f$ in column 6. Note, this is the time spent to identify the top candidates and the remaining time is spent to identify the best candidate using accurate evaluation of $MSRR$ through X-Simulation. As can be seen, this runtime is a negligible fraction of the total runtime, e.g., only 1 minute out of 28 minutes in {\tt dsp}.

The runtime of IteM is reported in column 6 which includes the runtime to generate the initial solution. The amount of time to generate
the initial solution in IteM has already been reported in column 3 which is the runtime of HYBR. (Recall, we used HYBR to generate the single-mode optimized initial solution in IteM.) We note, our implementation of HYBR includes an improvement to incrementally update consecutive restoration maps during the forward-greedy selection process which significantly improves the runtimes of HYBR.

%This shows the effectiveness of our approach in finding a suitable
%$m_{start}$. Note this runtime includes both the time to find $m_{start}$
%as well as the time to generate a complete solution using the SMTS
%procedure given in \cite{LiD13,LiD14TCAD}. (We further improved the implementation
%of \cite{LiD13,LiD14TCAD} using an incremental update in the restoration maps in
%consecutive iterations of forward-greedy selection. This incremental
%update helped improve the runtime. We use this same implementation of
%\cite{LiD13,LiD14TCAD} in all variations of trace signal selection strategies in this work.)

When looking into the individual runtime of IteM for each benchmark, it can be seen that {\tt dsp} has a much longer runtime than the others. This is because the initial solution generated by HYBR is not as good as the other benchmarks, as can be verified from the solution quality reported in Table \ref{tab:msrr} for this benchmark. Therefore IteM takes more iterations to improve upon the initial solution results.

%The number of iterations in IteM is reported in column 7. The runtime of IteM and number of iterations are determined by the termination condition of the algorithm. Recall IteM terminates when improvement in $MSSR$ is not found within 20 consecutive iterations.

Overall, we consider the runtime of IteM reasonable given the large size of most of the benchmarks and emphasize that IteM provides significantly better solution quality compared to the faster techniques.

\subsection{Impact of Mode Merging}
To show that the mode merging can actually help reduce the runtime of IteM
with a little degradation in the solution quality in terms of MSRR, we
apply IteM to the three benchmarks {\tt S35932}, {\tt DMA}, {\tt dsp} which
reduce the total number of modes from 4 to 2, 8 to 4 and 8 to 2
respectively as shown in Table \ref{tab:benchinfo}. Specifically, we
randomly pick one mode within each group of merged modes as the
representative mode that is considered during the IteM process and report
the results in Figure \ref{fig:mm_impact}.

\begin{figure}[t]
\centering
    \includegraphics[width=4.5in]{figs/MM_impact.pdf}
    \caption{Impact of Mode Merging on MSRR and Runtime}
    \label{fig:mm_impact}
\end{figure}

Here, we compare the solution quality and runtime when mode merging is
applied and not applied. Solution quality in terms of SRR is shown in
histogram, corresponding to the left Y-axis, while the runtime in hours is
shown in scatter points connected by lines, corresponding to the right
Y-axis.  For {\tt S35932}, the runtimes with/without mode merging are
almost the same due to the small size of the benchmark which makes the
algorithm run too quickly to show a noticeable difference. The
solution quality for this benchmark is degraded by 3.5\%. Then for
{\tt DMA}, we notice a more significant runtime reduction by 43.4\% after
mode merging. The MSRR degradation is also negligible which is only
2.5\%. For {\tt dsp}, there is a big runtime reduction which is around 4X
when mode merging is applied. This is because {\tt dsp} has
the most reduction in terms of the number of modes, from 8 to 2. The
solution quality degradation is slightly more compared to the other
two benchmarks, which drops by 3.8\%.

To sum up, mode merging can help significantly reduce the runtime when
the size of the benchmarks is relatively large (such as the ones in ISPD'12
\cite{ISPD12} and IWLS'05 \cite{IWLS05}) and mode reduction can greatly
reduce the total number of modes (such as for {\tt dsp}, in which the
number of modes reduces from 8 to 2). The solution quality in terms of MSRR
will degrade as the number of modes reduced, but this degradation is
usually quite small. 

\subsection{Impact of the Swapping Procedure}
%Here, we show the effectiveness of the search strategy in IteM. 
Recall that each iteration of IteM considers swapping with increasing
perturbation of radius $R=1$ up to a maximum radius of $R=3$.  The swaps
are first considered using (deterministic) elimination of the least
promising trace, and if the acceptance criteria is not satisfied, the
process repeats but this time random elimination is used in each swap. The
iteration stops as soon as the acceptance criteria is satisfied and the
corresponding swap (with the corresponding radius) is enforced.

To show these strategies were all useful in IteM, in Figure
\ref{fig:ratio_moves} we reported the percentage of the iterations which
stopped at a given radius (further divided into deterministic and random
cases) in benchmark {\tt S35932}. The X-axis shows the corresponding 6
cases. For example, D2 and R2 show the percentages of iterations in which
two trace signals were swapped using deterministic and random eliminations,
respectively. As can be seen, the maximum number of swaps was using D1 (one
state element/deterministic) which happened in about 36\% of the
iterations. The minimum was D3 in 6\% of the iterations, and interestingly
the remaining cases (including random swaps) each had higher than 10\% of
the iterations.

\begin{figure}[t]
\centering
    \includegraphics[width=2.7in]{figs/ratio_moves.eps}
    \caption{Ratio of number of swaps (Y-Axis) and swap types (X-Axis)}
    \label{fig:ratio_moves}
\end{figure}


\exclude{
Here we conduct our last experiment to analyze IteM. Recall from Table \ref{tab:msrr} that we observed that on average 41\% of the state elements were shared among the initial solution, before the swaps were applied and the final solution. Interestingly often times, state elements were eliminated and then brought back in the future swaps. Figure \ref{fig:ratio-return} reports the percentage of the state elements which were eliminated and then returned at least once throughout the algorithm for all the benchmarks. This ratio is often quite high except for the {\tt des\_perf} where we suspect the low ratio is because of the smaller number of iterations of the algorithm. Overall, this experiment is an indication of the effectiveness of the algorithm in considering all the state elements as candidates for trace signal for optimizing the multi-mode restorability.}



% LocalWords:  MMTS ConM
